/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.Stack;

/**
 * <p>
 * 实现二叉排序树迭代器
 *  next() will return the next smallest number in the BST.
 *  next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月14日
 */
public class BSTIterator{
    
    private Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        //压入最左节点，栈头是最小值
        pushLeft(root);
    }

    /**
     * @param x
     * @author towan
     * 2015年6月14日
     */
    private void pushLeft(TreeNode x) {
        while(x!=null){
            stack.push(x);
            x = x.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode x = stack.pop();
        //找出栈头中序遍历的下一个节点
        pushLeft(x.right);
        return x.val;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode left = new TreeNode(3);
        root.left = left;
        TreeNode right = new TreeNode(7);
        root.right = right;
        left.left = new TreeNode(1);
        left.right = new TreeNode(4);
        right.right = new TreeNode(9);
        
        BSTIterator iterator = new BSTIterator(root);
        int next = iterator.next();
        System.out.println(next);
        System.out.println(iterator.next());
    }
}
